// 142. 环形链表 II
// 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 
// 如果链表无环，则返回 null。
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
// 思路：判断链表是否有环
// 可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，
// fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，
// 说明这个链表有环。
// 判断环的入口
// 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点，
// 那么当这两个指针相遇的时候就是 环形入口的节点。
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var detectCycle = function(head) {
    let fast=head,slow=head;
    while(fast!=null){
        if(fast.next==null){// fast.next走出链表了，说明无环
            return null;
        }
        fast=fast.next.next;// 快指针走两步
        slow=slow.next;// 慢指针走一步
        if(slow==fast){ // 首次相遇
            fast=head;// 让快指针回到头节点
            while(true){ // 开启循环，让快慢指针相遇
                if(slow==fast){ // 相遇，在入环处
                    return slow;
                }
                fast=fast.next;// 快慢指针都走一步
                slow=slow.next;
            }
        }
    }
    return null;
};

// 141. 环形链表
// 给你一个链表的头节点 head ，判断链表中是否有环。
// 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
 var hasCycle = function(head) {
    let fast=head,slow=head;
    while(fast){
        if(fast.next==null){
            return false;
        }
        fast=fast.next.next;
        slow=slow.next;
        if(slow==fast){
            return true;
        }
    }
    return false;
};